package algorithme;

import model.Arc;
import model.Graph;
import model.Noeud;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * User: Thomas
 * Date: 04/02/14
 * Time: 10:56
 */
public class AlgorithmeBellmanFord extends AlgorithmePlusCourtChemin {

    /**
     * Recherche le plus court chemin par l'algorithme de Bellman Ford
     * @param graph le graph dans lequel se situe la recherche
     * @param source le noeud de départ
     * @param destination le noeud de destination
     * @return la liste chainée de destination vers la source
     */
    @Override
    protected LinkedListNoeudPath plusCourtChemin(Graph graph, Noeud source, Noeud destination) {
        //Initialisation du tableau des distances
        HashMap<Integer, LinkedListNoeudPath> distances = this.initTableauDistance(graph,source);

        //parcours de tous les noeuds du graph
        for (int i = 1; i < graph.getNoeuds().size(); i++) {
            //condition d'arret
            boolean poids_inchange = true;

            //Parcours de tous les arcs du graph
            for(Map.Entry<String, ArrayList<Arc>> arcs : graph.getArcs().entrySet()) {
                for (Arc arc : arcs.getValue()) {

                    //LinkedListNoeudPath de destination de l'arc courant
                    LinkedListNoeudPath destinationLinked = distances.get(arc.getDestination().getId());
                    //LinkedListNoeudPath de source de l'arc courant
                    LinkedListNoeudPath sourceLinked = distances.get(arc.getSource().getId());

                    double d = sourceLinked.getDistance() + arc.getCout();

                    //si la distance est plus courte ou si la distance est égal et qu'il y a moins de correspondance
                    if ( d < destinationLinked.getDistance() ||
                            (d == destinationLinked.getDistance() && destinationLinked.getNbCorrespondance() > sourceLinked.getNbCorrespondance()) ) {
                        destinationLinked.setDistance(d);
                        poids_inchange = false;

                        //on modifie ou on ajoute un prédécesseur
                        destinationLinked.setPrevious(sourceLinked);
                        destinationLinked.setArc(arc);

                        //si l'arc courant est une correspondance on incrémente
                        if (arc.getLigne().equals("0")) {
                            destinationLinked.setNbCorrespondance(sourceLinked.getNbCorrespondance() + 1);
                        } else {
                            destinationLinked.setNbCorrespondance(sourceLinked.getNbCorrespondance());
                        }
                    }
                }
            }
            //arret si aucun changement n'a eu lieu
            if (poids_inchange) {
                break;
            }
        }

        //parcours du chemin trouvé à l'envers, destination -> source
        return distances.get(destination.getId());
    }
}
